package com.otherTest.datastructure.tree.binarysearchtree;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * @Description: 二叉搜索树
 *               <p>
 *               二叉树：树的每个节点最多只能有两个子节点 左子树上所有结点的值均小于它的根结点的值 右子树上所有结点的值均大于它的根结点的值
 *               称作二叉搜索树(binary search tree)的特殊二叉树
 *
 * @author: conceit
 * @Date: 2018/11/5 13:58
 */
public class BinarySearchTree {

    public BinarySearchTreeNode root;

    /***
     * 新增节点 根节点不为空的 大于右侧节点则向下继续寻找为null插入 小于则在左侧同样处理
     *
     * @param key
     * @return
     */
    public boolean insert(Integer key) {
        // root节点为空则新增root
        if (Objects.isNull(root)) {
            root = new BinarySearchTreeNode(key);
            return true;
        } else {
            // root节点作为当前起始节点
            BinarySearchTreeNode current = root;
            // 申明当前节点的父级节点
            BinarySearchTreeNode parentNode = null;

            // 遍历每个节点,每遍历层次加一，current也需要同步
            while (Objects.nonNull(current)) {
                // 每循环一次，tree的层次便加1
                parentNode = current;
                int compare = current.getData().compareTo(key);
                switch (compare) {
                case 1:
                    current = current.getLeft();
                    if (Objects.isNull(current)) {
                        // 当前节点已经向下走了一个层级
                        // 所以在循环开始处，将current赋值给parentNode
                        parentNode.setLeft(new BinarySearchTreeNode(key));
                        return  true;
                    }
                case -1:
                    current = current.getRight();
                    if (Objects.isNull(current)) {
                        parentNode.setRight(new BinarySearchTreeNode(key));
                        return  true;
                    }
                case 0:
                    return true;
                }
            }

        }
        return  false;
    }

    /**
     * 寻找节点，需要从根节点开始寻找 大于则从左侧开始寻找 小于则从右侧开始寻找 等于则终止寻找
     *
     */
    public BinarySearchTreeNode find(Integer key) {
        BinarySearchTreeNode current = root;
        while (true) {
            int compare=current.data.compareTo(key);
            switch (compare){
                //寻找值小于current.则去左侧寻找
                case 1:
                    current=current.left;
                //反之
                case -1:
                    current=current.right;
                case 0:
                    return current;
                default:
                    return null;
            }
        }
    }

    /**
     * 求出该节点下的子节点总数
     *
     * @param node
     * @return
     */
    public Long nodeNum(BinarySearchTreeNode node) {
        return this.preOrderNonRecursive(node).stream().count();
    }

    /**
     * 删除方法最为复杂
     *
     * @param key
     * @return
     */
    public boolean delete(Integer key) {
        return true;
    }

    /**
     * 前序遍历:根节点——》左子树——》右子树
     * 使用非递归方式 堆-后进先出 先将根结点压栈，在栈不为空的时候执行循环：
     * 让栈顶元素p出栈，访问栈顶元素p， 如果p的右孩子不为空，则让其右孩子先进栈， 如果p的左孩子不为空，则再让其左孩子进栈
     * 注意：进栈顺序一定是先右再左--ok
     * <p>
     * <p>
     * 执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。 执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
     * 执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。
     *
     * @return
     */
    public List<Integer> preOrderNonRecursive(BinarySearchTreeNode node) {
        Stack<BinarySearchTreeNode> stack = new Stack<BinarySearchTreeNode>();
        List<Integer> result = new ArrayList<Integer>();


        return result;
    }

    /**
     * 前序遍历:根节点——》左子树——》右子树
     * 使用递归完成前序遍历
     *
     * @param node
     * @return
     */
    public List<Integer> preOrder(BinarySearchTreeNode node) {
        List<Integer> result =null;
        if(Objects.nonNull(node)){
            if(Objects.nonNull(node.left)){
                List<Integer> leftResult=this.preOrder(node.left);
                result.addAll(leftResult);
            }
            if(Objects.nonNull(node.right)){
                List<Integer> rightResult=this.preOrder(node.right);
                result.addAll(rightResult);
            }
        }
        
        return result;
    }

    /**
     * 中序遍历 中序遍历:左子树——>根节点——>右子树 二叉搜索树最常用的是中序遍历
     *
     * @return
     */
    public List<Integer> midOrder(BinarySearchTreeNode node) {

        return null;
    }

    /**
     * 后序遍历 后序遍历:左子树——>右子树——>根节点
     *
     * @return
     */
    public Integer[] laterOrder(BinarySearchTreeNode node) {

        return null;
    }

}
